package DP;

import java.util.Scanner;

/**
 * @author dx
 * @version 1.0
 * @date 2022/5/17 15:14
 * @description: 力扣198 打家劫舍
 */
public class Rob {
    public static void main(String[] args) {
        int [] arr = {1,2,3,1};
        System.out.println(new Rob_Solution().rob(arr));
    }
}

class Rob_Solution{
//    int max[] = new int[1];
//    int [] sum = new int[1];
//    public int rob(int[] nums) {
//        int t = 0;
//        max[0] = -1;
//        sum[0] = 0;
//        backtrace(nums,max,sum,t);
//
//        return max[0];
//    }
//    public void backtrace(int []nums,int []max,int []sum,int t){
//
//        if(t == nums.length-1){
//            max[0] = Math.max(sum[0],max[0]);
//            System.out.println(sum[0]);
//            return;
//        }
//        for(int i = 0;i<nums.length;i++){
//            if((i - t <= 1)){
//                continue;
//            }
//            sum[0] += nums[i];
//            backtrace(nums,max,sum,i);
//        }
//    }

    public int rob(int[] nums){

        if(nums.length == 1){
            return nums[0];
        }
        int []dp = new int[nums.length];

        dp[0] = nums[0];
        dp[1] = Math.max(dp[0],nums[1]);
        if(nums.length ==2){
            return dp[1];
        }
        for(int i = 2;i < nums.length;i++){
            dp[i] = Math.max(dp[i-2]+nums[i],dp[i-1]);
        }
        return dp[nums.length-1];
    }
}